package LRU;

import java.util.*;

public class Solution {
    public class LRUCache {
        class DLinkedNode {
            int key;
            int value;
            DLinkedNode prev;
            DLinkedNode next;
            public DLinkedNode() {}
            public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
        }

        private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
        private int size;
        private int capacity;
        private DLinkedNode head, tail;

        public LRUCache(int capacity) {
            this.size = 0;
            this.capacity = capacity;
            // 使用伪头部和伪尾部节点
            head = new DLinkedNode();
            tail = new DLinkedNode();
            head.next = tail;
            tail.prev = head;
        }

        public int get(int key) {
            DLinkedNode node = cache.get(key);
            if (node == null) {
                return -1;
            }
            // 如果 key 存在，先通过哈希表定位，再移到头部
            moveToHead(node);
            return node.value;
        }

        public void put(int key, int value) {
            DLinkedNode node = cache.get(key);
            if (node == null) {
                // 如果 key 不存在，创建一个新的节点
                DLinkedNode newNode = new DLinkedNode(key, value);
                // 添加进哈希表
                cache.put(key, newNode);
                // 添加至双向链表的头部
                addToHead(newNode);
                ++size;
                if (size > capacity) {
                    // 如果超出容量，删除双向链表的尾部节点
                    DLinkedNode tail = removeTail();
                    // 删除哈希表中对应的项
                    cache.remove(tail.key);
                    --size;
                }
            }
            else {
                // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
                node.value = value;
                moveToHead(node);
            }
        }

        private void addToHead(DLinkedNode node) {
            node.prev = head;
            node.next = head.next;
            head.next.prev = node;
            head.next = node;
        }

        private void removeNode(DLinkedNode node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }

        private void moveToHead(DLinkedNode node) {
            removeNode(node);
            addToHead(node);
        }

        private DLinkedNode removeTail() {
            DLinkedNode res = tail.prev;
            removeNode(res);
            return res;
        }
    }
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
    public class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
  }
    public int numColor(TreeNode root) {
        //
        if(root == null)return 0;
        Set<Integer> set = new HashSet<>();
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()){
            set.add(queue.peek().val);
            if(queue.peek().left!=null){
                queue.add(queue.peek().left);
            }
            if(queue.peek().right!=null){
                queue.add(queue.peek().right);
            }
            queue.poll();
        }
        return set.size();
    }
    public int minNumBooths(String[] demand) {
        int[] cnt = new int[26];
        int ans = 0;
        for (String s: demand) {
            int[] tmp = new int[26];
            for (char c: s.toCharArray()) {
                tmp[c-'a']++;
            }
            for (int i = 0; i < 26; i++) {
                if(cnt[i]<tmp[i]) {
                    cnt[i] = tmp[i];
                }
            }
        }
        return Arrays.stream(cnt).sum();
    }
    public boolean isAnagram(String s, String t) {
        if(s.equals(t))return false;
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); i++) {
            cnt[s.charAt(i)-'a']++;
        }
        for (int i = 0; i < t.length(); i++) {
            if(cnt[t.charAt(i)-'a'] == 0) return false;
            cnt[t.charAt(i)-'a']--;
        }
        return Arrays.stream(cnt).sum() == 0;
    }
    public String maximumOddBinaryNumber(String s) {
        // 最后一个是1 其它的放在前面
        StringBuilder sb = new StringBuilder();
        int oneCount = 0;
        int zeroCount = 0;
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '0'){
                zeroCount++;
            } else {
                oneCount++;
            }
        }
        oneCount--;
        sb.append('1');
        while (zeroCount>0) {
            zeroCount--;
            sb.append('0');
        }
        while (oneCount>0){
            oneCount--;
            sb.append('1');
        }
        return sb.reverse().toString();
    }
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int[] cnt = new int[1001];
        for (int i = 0; i < arr1.length; i++) {
            cnt[arr1[i]]++;
        }
        int index = 0;
        int[] ans = new int[arr1.length];
        for (int i = 0; i < arr2.length; i++) {
            while (cnt[arr2[i]]>0) {
                cnt[arr2[i]]--;
                ans[index++] = arr2[i];
            }
        }
        // 每出现的元素
        for (int i = 0; i < cnt.length; i++) {
            while (cnt[i]>0) {
                ans[index++] = i;
                cnt[i]--;
            }
        }
        return ans;
    }
    public int findRepeatDocument(int[] documents) {
//        Set<Integer> set = new HashSet<>();
//        for (int d: documents) {
//            if(!set.add(d)) {
//                return d;
//            }
//        }
//        return 0;

        // 原地哈希
        int i = 0;
        while (i<documents.length){
            if(documents[i] == i) {
                i++;
                continue;
            }
            if(documents[documents[i]] == documents[i]) {
                return documents[i];
            }
            int tmp = documents[i];
            documents[i] = documents[documents[i]];
            documents[tmp] = tmp;
        }
        return -1;
    }

    // KMP算法
    public int strStr(String haystack, String needle) {
        int n = haystack.length(),m = needle.length();
        if(m == 0){
            return 0;
        }
        int[] next = getNext(needle);
        for (int i = 0,j = 0; i < n; i++) {
            while (j>0&&haystack.charAt(i) != needle.charAt(j)) {
                j = next[j-1];
            }
            if(haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if(j == m){
                return i-m+1;
            }
        }
        return -1;
    }
    private int[] getNext(String s){
        int n = s.length();
        int[] next = new int[n];
        for (int i = 1,j = 0; i < n; i++) {
            while (j>0&&s.charAt(j) != s.charAt(i)) {
                j = next[j-1];
            }
            if(s.charAt(i) == s.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // 合并两个有序数组
        int index = m+n-1;
        int i = m-1,j = n-1;
        while (i>=0||j>=0){
            if(i<0){
                nums1[index--] = nums2[j--];
            } else if (j<0) {
                nums1[index--] = nums1[i--];
            } else if (nums1[i]<nums2[j]) {
                nums1[index--] = nums2[j--];
            } else {
                nums1[index--] = nums1[i--];
            }
        }
    }
    public boolean isPalindrome(String s) {
        int n = s.length();
        int left = 0, right = n - 1;
        while (left < right) {
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                ++left;
            }
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                --right;
            }
            if (left < right) {
                if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                    return false;
                }
                ++left;
                --right;
            }
        }
        return true;
    }
    public boolean hasCycle(ListNode head) {
        // 快慢指针
        if(head == null) return false;
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast!=null&&fast.next!=null) {
            if(fast == slow) return true;
            slow = slow.next;
            fast = fast.next.next;
        }
        return false;
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pA = headA;
        ListNode pB = headB;
        while (pA!=pB){
            pA = pA == null?headB:pA.next;
            pB = pB == null?headA:pB.next;
        }
        return pA;
    }
    public boolean isHappy(int n) {
        // 会出现循环
        // 会出现环
        // 快慢指针
        int slow = n;
        int fast = getNext(n);
        while (fast!=1&&slow!=fast){
            slow = getNext(slow);
            fast = getNext(getNext(fast));
        }
        return fast == 1;
    }
    private int getNext(int n) {
        int totalSum = 0;
        while (n>0){
            totalSum+=(n%10)*(n%10);
            n/=10;
        }
        return totalSum;
    }
    public void moveZeroes(int[] nums) {
        int n = nums.length, left = 0, right = 0;
        while (right < n) {
            if (nums[right] != 0) {
                swap(nums, left, right);
                left++;
            }
            right++;
        }
    }
    public void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
//    ListNode p;
//    boolean ans = true;
//    public boolean isPalindrome(ListNode head) {
//        p = head;
//        dfs(head);
//        return ans;
//    }
//    private void dfs(ListNode cur){
//        if(cur == null) {
//            return;
//        } else {
//            dfs(cur.next);
//        }
//        if(p.val!=cur.val) {
//            ans = false;
//        }
//        p = p.next;
//    }
}
